package demo2;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //交易逆序对的总数
    int ret = 0;
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return ret;
    }

    private void mergeSort(int[] nums,int left,int right){
        if(left>=right) return;
        int j = 0;
        int mid = (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        int pcur1 = left; int pcur2 = mid+1;
        while (pcur1 <= mid && pcur2 <= right) {
            if(nums[pcur1]>nums[pcur2]){
                tmp[j++] = nums[pcur2++];
                ret += mid - pcur1 +1;
            }else {
                tmp[j++] = nums[pcur1++];
            }
        }
        while(pcur1 <= mid){
            tmp[j++] = nums[pcur1++];
        }
        while(pcur2 <= right){
            tmp[j++] = nums[pcur2++];
        }
        for(int i = left,k=0;i<=right;i++,k++){
            nums[i] = tmp[k];
        }
    }

    public static void main1(String[] args) {
        TreeNode root =  new TreeNode(0);
        //isValidBST(root);
    }


    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean validate(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return  validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}
